package org.cllib.algorithm;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
	public static void main(String[] args) {
		Random r = new Random();
		
		for (int j = 0; j < 10000000; j++) {
			int[] array = new int[r.nextInt(100) + 10];
			for (int i = 0; i < array.length; i++) {
				array[i] = r.nextInt(50);
			}
			
			int offset = r.nextInt(array.length);
			int length = r.nextInt(array.length - offset);
			
			int[] copy = new int[length];
			System.arraycopy(array, offset, copy, 0, length);
			
			QuickSort.sort(array , offset , length);
			Arrays.sort(copy);
			
			for (int i = offset; i < offset + length; i++) {
				if(array[i] != copy[i - offset]){
					throw new IllegalStateException();
				}
			}
			
		}
		
		System.out.println("ok");
	}
	
	public static void sort(final int[] array){
		sort(array, 0, array.length);
	}
	
	public static void sort(final int[] array ,final int offset ,final int length){
		quickSort(array , offset , length);
	}
	
	private static void quickSort(final int[] array , int offset , int length){
		if(length > 1){
			final int p = partition(array, offset, length);
			quickSort(array, offset, p - offset);
			quickSort(array, p + 1, offset + length - 1 - p);
		}
	}
	
	private static int partition(final int[] array ,final int offset ,final int length){
		if(length > 1){
			int flagIndex = offset + length - 1;
			final int flag = array[flagIndex];
			
			int index = 0;
			for (int i = offset; i < offset + length - 1; i++) {
				if(array[i] > flag){
					int bigIndex = offset + length - 2;
					while(array[bigIndex] >= flag && bigIndex > i){
						bigIndex -- ;
					}
					
					if(bigIndex <= i){
						//no more small elements found
						int temp = array[offset + index];
						array[offset + index] = flag;
						array[flagIndex] = temp;
						
						flagIndex = offset + index;
						break;
					}else{
						int temp = array[i];
						array[i] = array[bigIndex];
						array[bigIndex] = temp;
					}
				}
				
				index ++;
			}
			
			return flagIndex;
		}else{
			return offset;
		}
	}
}
